package hash;

import java.util.NoSuchElementException;

public class MyHashMap {
    //有效元素个数
    private int size;
    // 实际存储元素的Node数组
    private Node[] hashTable;
    // 取模数
    private int M;
    // 负载因子
    private static final double LOAD_FACTOR = 0.75;
    public MyHashMap() {
        this(16);
    }

    public MyHashMap(int init) {
        this.hashTable = new Node[init];
        this.M = init;
    }

//对key求哈希
    public int hash(int key){
        return Math.abs(key)%M;
    }

    //将一对键值对保存到当前hash表中
    public int put(int key,int val){
        // 1.先对key取模
        int index = hash(key);
        // 2.遍历这个index对应链表，查看key是否存在
        for (Node x = hashTable[index];x!=null;x=x.next){
            if (x.key == key){
                int oldVal = x.value;
                x.value = val;
                return oldVal;
            }
        }
        // 3.此时整个链表中不包含相应key的结点，头插到当前位置
        Node node =new Node(key,val);
        // 头结点 hashTable[index]
        node.next = hashTable[index];
        hashTable[index] = node;
        size++;
        if (size>=hashTable.length*LOAD_FACTOR){
            resize();
        }
        return val;
    }

    //判断当前key是否在表中存在
    public boolean cotainsKey(int key){
        int index = hash(key);
        for (Node x = hashTable[index];x!=null; x=x.next){
            if (x.key==key){
                return true;
            }
        }
        return false;
    }

    //判断value是否存在
    public boolean cotainsValue(int value){
        // 全表扫描
        for (int i = 0; i < hashTable.length; i++) {
            for (Node x= hashTable[i];x!=null;x = x.next){
                if (x.value==value){
                    return true;
                }
            }
        }
        return false;
    }

    //在哈希表中删除指定的键值对(key,value)
    public boolean remove(int key,int value){
        int index = hash(key);
        // 判断头节点是否是待删除节点
        Node head = hashTable[index];
        if (head.key==key&&head.value==value){
            hashTable[index]=head.next;
            head=head.next=null;
            size--;
            return true;
        }
        Node prve=head;
        while (prve.next!=null){
            if (prve.next.key==key&&prve.next.value==value){
                // prev恰好是待删除节点的前驱
                Node cur = prve.next;
                prve.next=cur.next;
                cur=cur.next=null;
                size--;
                return true;
            }else {
                prve=prve.next;
            }
        }
        // 哈希表没有这个节点
        throw new NoSuchElementException("no such node!!remove error");
    }



    //哈希表的扩容方法，新数组的长度变为原来的一倍
    private void resize(){
        // 1.产生一个新数组且新数组长度变为原来的一倍
        Node[] newTable = new Node[hashTable.length<<1];
        // 2.进行元素的搬移操作，将原数组中的所有元素搬移到新数组中,
        // 此时取模数变为新数组的长度
        this.M= newTable.length;
        //3.进行元素搬移
        for (int i = 0; i < hashTable.length; i++) {
            for (Node x=hashTable[i];x!=null;){
                //将X搬移到新数组的位置
                Node next = x.next;
                //新数组头插
                int index = hash(x.key);
                x.next=newTable[index];
                newTable[index]=x;
                //继续搬移原数组的后继结点
                x=next;
            }
        }
        hashTable=newTable;
    }


}

// 当前哈希表中保存的结点，key = value的键值对对象
class Node {
    // 对key进行hash运算
    int key;
    int value;
    // 下一个节点地址
    Node next;

    public Node(int key, int val) {
        this.key = key;
        this.value = value;
    }
}